package com.leetcode.algorithm.y18.m05;

/**
 * leetcode-cn.com
 * 387. 字符串中的第一个唯一字符
 * 400. 第N个数字
 * 415. 字符串相加
 * @author dengjie213@126.com
 * 2018年5月13日 下午9:54:10
 */
public class MySolution0513 {
	/**
	 * 400. 第N个数字 
	 * 在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
	 * 
	 * 注意: 
	 * n 是正数且在32位整型范围内 。
	 * 
	 * 示例 1:
	 * 输入: 3
	 * 输出: 3 
	 * 
	 * 示例 2:
	 * 输入: 11
	 * 输出: 0
	 * 说明: 第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。
	 * 
	 * @param n
	 * @return
	 */
    public int findNthDigit(int n) {
		// 9
		// 9 + 90*2 = 189
		// 9 + 90*2 + 900*3 = 2889
		// 9 + 90*2 + 900*3 + 9000*4= 38889
		// 9 + 90*2 + 900*3 + 9000*4 + 90000*5= 488889
		int i = 1;
		int mul = 1;
		while (n/9 >= mul * i) {
			n = n - 9 * mul * i;
			i++;
			mul *= 10;
		}
		int num = mul - 1;
		num += (n / i);
		int j = n % i;
		if (j == 0) {
			return num % 10;
		}else {
			num += 1;
			for (int j2 = 1; j2 < j; j2++) {
				num -= num / mul * mul;
				mul /= 10;
			}
			return num/mul;
		}
    }
    
    /**
	 * 387. 字符串中的第一个唯一字符
	 * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
	 * 
	 * 案例:
	 * s = "leetcode" 返回 0.
	 * s = "loveleetcode", 返回 2.
	 * 
	 * 注意事项：您可以假定该字符串只包含小写字母。
	 * 
	 * @param s
	 * @return
	 */
	public int firstUniqChar(String s) {
		if (null == s || "".equals(s)) {
			return -1;
		}
		char[] chars = s.toCharArray();
		int len = chars.length;
		boolean[] arr1 = new boolean[26];
		for (int i = 0; i < len; i++) {
			char ch = chars[i];
			int idx = ch - 'a';
			if (arr1[idx]) {
				continue;
			}
			boolean repeatFlag = false;
			for (int j = i + 1; j < len; j++) {
				if (chars[j] == ch) {
					repeatFlag = true;
					break;
				}
			}
			if (!repeatFlag) {
				return i;
			} else {
				arr1[idx] = true;
			}
		}
		return -1;
	}
    
    /**
	 * 415. 字符串相加 
	 * 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
	 * 
	 * 注意：
	 * num1 和num2 的长度都小于 5100. 
	 * num1 和num2 都只包含数字 0-9. 
	 * num1 和num2 都不包含任何前导零。
	 * 你不能使用任何內建 BigInteger库， 也不能直接将输入的字符串转换为整数形式。
	 * 
	 * @param num1
	 * @param num2
	 * @return
	 */
	public String addStrings(String num1, String num2) {
		char[] chars1 = num1.toCharArray();
		char[] chars2 = num2.toCharArray();
		int len1 = chars1.length;
		int len2 = chars2.length;
		int len = Math.max(len1, len2);
		char[] chars = new char[len + 1];
		int ch = 0;// 进位
		for (int k = 1; k <= len; k++) {
			int i = len1 - k, j = len2 - k;
			int i1 = (i >= 0) ? (chars1[i] - '0') : 0;
			int i2 = (j >= 0) ? (chars2[j] - '0') : 0;
			int num = i1 + i2 + ch;
			ch = num >= 10 ? 1 : 0;
			chars[len + 1 - k] = (char) (num % 10 + '0');
		}
		if (ch == 0) {
			return new String(chars, 1, len);
		} else {
			chars[0] = '1';
			return new String(chars);
		}
	}
    
}
